package leetcode.code1286;

public class CombinationIterator {

	private int[] ans;
	private int ANSLEN;
	private char[] chars;
	private int CHARSLEN;
	private boolean hasNext;
	private int p;
	private int DIFF;
	private int LAST;

	public CombinationIterator(String characters, int combinationLength) {
		this.ANSLEN = combinationLength;
		this.LAST = this.ANSLEN - 1;
		this.chars = characters.toCharArray();
		this.CHARSLEN = chars.length;
		this.hasNext = true;
		this.DIFF = this.CHARSLEN - this.ANSLEN;
		this.ans = new int[this.ANSLEN];
		for (p = 0; p < this.ANSLEN; p++) {
			this.ans[p] = p;
		}
		this.p = this.LAST;
	}

	public String next() {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < this.ANSLEN; i++) {
			sb.append(this.chars[this.ans[i]]);
		}
		this.move2next();
		return sb.toString();
	}

	private void move2next() {
		if (this.ans[p] != DIFF + p) {
			this.ans[p]++;
		} else {
			while (p >= 0 && this.ans[p] == DIFF + p) {// 找到最近一个可以向后移动的较高位置
				p--;
			}
			if (p >= 0 && this.ans[p] != DIFF + p) {
				this.ans[p]++;
				for (p = p + 1; p < this.ANSLEN; p++) {
					this.ans[p] = this.ans[p - 1] + 1;
				}
				this.p = this.LAST;
				return;
			} else {
				this.hasNext = false;
				return;
			}
		}
	}

	public boolean hasNext() {
		return this.hasNext;// 不到结尾就hasNext
	}

	public static void main(String[] args) {
		CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator
		String ans = null;
		boolean b = false;
		ans = iterator.next(); // 返回 "ab"
		System.out.println(ans);
		b = iterator.hasNext(); // 返回 true
		System.out.println(b);
		ans = iterator.next(); // 返回 "ac"
		System.out.println(ans);
		b = iterator.hasNext(); // 返回 true
		System.out.println(b);
		ans = iterator.next(); // 返回 "bc"
		System.out.println(ans);
		b = iterator.hasNext(); // 返回 false
		System.out.println(b);
	}

}
